package com.nine.algorithm.linklist;

import java.util.Iterator;
import java.util.function.Consumer;

/**
 * @author nine
 * @version 1.0
 * @description 单向链表（带哨兵）
 * @date 24/4/26 21:09
 */
public class SinglyLinkedListSentinel implements Iterable<Integer> {

	// 头指针 - 哨兵节点
	private Node head = new Node(666, null);

	/**
	 * 向链表头部添加
	 *
	 * @param value
	 */
	public void addFirst(int value) {
		insert(0, value);
	}

	/**
	 * 循环遍历链表
	 *
	 * @param consumer
	 */
	public void loop(Consumer<Integer> consumer) {
		// 存在哨兵的情况下，第一个节点应该是哨兵的下一个
		Node p = head.next;
		while (p != null) {
			consumer.accept(p.value);
			p = p.next;
		}
	}

	/**
	 * 循环遍历方法二
	 *
	 * @param consumer
	 */
	public void loop2(Consumer<Integer> consumer) {
		// 存在哨兵的情况下，第一个节点应该是哨兵的下一个
		for (Node p = head.next; p != null; p = p.next) {
			consumer.accept(p.value);
		}
	}

	/**
	 * 循环遍历方法三
	 *
	 * @return
	 */
	@Override
	public Iterator<Integer> iterator() {
		return new NodeIterator();
	}

	private Node findLast() {
		// 空链表，存在哨兵的情况下，不会出现null
		// if (head == null) {
		// 	return null;
		// }
		Node p;
		for (p = head; p.next != null; p = p.next) {
		}
		return p;
	}

	public void addLast(int value) {
		// 先找到最后一个节点
		Node last = findLast();
		// 存在哨兵的情况下，不会出现null
		// if (last == null) {
		// 	addFirst(value);
		// 	return;
		// }
		last.next = new Node(value, null);
	}

	/**
	 * 查找节点数据
	 */
	public int get(int index) {
		Node node = findNode(index);
		if (node == null) {
			throw illegalIndex(index);
		}
		return node.value;
	}

	private static IllegalArgumentException illegalIndex(int index) {
		return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
	}

	private Node findNode(int index) {
		// 从 哨兵索引 -1 开始匹配
		int i = -1;
		// 第一个节点，是哨兵节点
		for (Node p = head; p != null; p = p.next, i++) {
			if (i == index) {
				return p;
			}
		}
		// 没找到
		return null;
	}

	/**
	 * 插入
	 */
	public void insert(int index, int value) {
		// 存在哨兵的情况下，第一个节点应该是哨兵的下一个
		// if (index == 0) {
		// 	addFirst(value);
		// 	return;
		// }
		// 找到上一个节点
		Node prev = findNode(index - 1);
		if (prev == null) {
			throw illegalIndex(index);
		}
		prev.next = new Node(value, prev.next);
	}

	public void removeFirst() {
		if (head == null) {
			throw illegalIndex(0);
		}
		head = head.next;
	}

	public void remove(int index) {
		// if (index == 0) {
		// 	removeFirst();
		// 	return;
		// }
		// 上一个节点
		Node prev = findNode(index - 1);
		if (prev == null) {
			throw illegalIndex(index);
		}
		// 被删除的节点
		Node removed = prev.next;
		if (removed == null) {
			throw illegalIndex(index);
		}
		prev.next = removed.next;
	}

	/**
	 * 通过匿名内部类进行转化而来，类没有加static
	 * 当使用外部类成员变量时，不能加static
	 */
	private class NodeIterator implements Iterator<Integer> {
		// 存在哨兵的情况下，第一个节点应该是哨兵的下一个
		Node p = head.next;

		// 是否有下一个元素
		@Override
		public boolean hasNext() {
			return p != null;
		}

		// 返回当前值，并指向下一个元素
		@Override
		public Integer next() {
			int val = p.value;
			p = p.next;
			return val;
		}
	}

	/**
	 * 节点类
	 */
	private static class Node {
		// 值
		int value;
		// 下一个节点指针
		Node next;

		public Node(int value, Node next) {
			this.value = value;
			this.next = next;
		}
	}

}
